package partition

//归并排序
/**
	规则：
		 1.判断长度等于且小于1时退出
		 2.将数组一分为二做递归排序
		 3.获取两个有序数组 建立新数组
		 4.将两个数组一一比较，小的放入新数组
		 5.返回新数组
**/

func Sort(v []int) {
	copy(v, partition(v))

}

func partition(v []int) []int {
	if len(v) < 2 { //判断长度等于且小于1
		return v
	}

	//拆分数组
	a := partition(v[0 : len(v)/2])
	b := partition(v[len(v)/2 : len(v)])
	//建立新数组长度是a+b
	c := make([]int, len(a)+len(b))

	ai := 0
	bi := 0

	//将两个数组一一比较，小的放入新数组
	for i := 0; i < len(c); i++ {

		if ai >= len(a) {
			c[i] = b[bi]
			continue
		}

		if bi >= len(b) {
			c[i] = a[ai]
			continue
		}

		if a[ai] < b[bi] {
			c[i] = a[ai]
			ai++
		} else {
			c[i] = b[bi]
			bi++
		}

	}

	return c
}
